// @algorithm @lc id=312 lang=cpp 
// @title burst-balloons

#define print(...)
// @test([3,1,5,8])=167
// @test([1,5])=10
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int> val{1, 1};
        val.insert(val.begin()+1, nums.begin(), nums.end());
        print("\ndata:", val, "\n")
        vector< vector<int> > dp(n+2, vector<int>(n+2, 0));
        for(int L=n-1; L>=0; L--){
            for(int R=L+2; R<n+2; R++){
                for(int m=L+1; m<R; m++){
                    int sum = val[L]*val[m]*val[R] + dp[L][m] + dp[m][R];
                    dp[L][R] = max(sum, dp[L][R]);
                }
            }
        }
        return dp[0][n+1];
    }
};